`:top

Ein `!In-Tree`! ist in der `F33f`_`[Graphentheorie`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graphentheorie]`_`f ein spezieller `F33f`_`[Graph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Graph_(Graphentheorie)]`_`f, genauer ein `F33f`_`[gewurzelter Baum`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Gewurzelter_Baum]`_`f.

>>Contents

• `F0af`_`[Definition`#definition]`_`f

• `F0af`_`[Weitere Begriffe`#weitere-begriffe]`_`f

• `F0af`_`[Alternative Definition`#alternative-definition]`_`f

-─

>>Definition

Ein `*In-Tree`* ist ein `F33f`_`[gerichteter Graph`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Gerichteter_Graph]`_`f mit einem ausgezeichneten Knoten, der so genannten `*Wurzel`*, für den im Gegensatz zu `F33f`_`[Out-Trees`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Out-Tree]`_`f gilt, dass die Wurzel von jedem Knoten aus durch genau einen `F33f`_`[gerichteten Pfad`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Gerichteter_Pfad]`_`f erreichbar ist.

>>Weitere Begriffe

Der maximale `F33f`_`[Eingangsgrad`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Eingangsgrad]`_`f eines In-Trees wird als seine `*Ordnung`* bezeichnet, und alle Knoten mit Eingangsgrad 0 nennt man Blätter. Als `*Höhe`* des In-Trees bezeichnet man die Länge eines längsten Pfades.

Wie bei `F33f`_`[ungerichteten Bäumen`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Ungerichteter_Baum]`_`f bezeichnet man auch in gewurzelten Bäumen alle Knoten, die kein Blatt sind, als `*innere Knoten`*. Manchmal schließt man die Wurzel dabei aber aus.

>>Alternative Definition

In-Trees lassen sich auch `F33f`_`[rekursiv`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Rekursion]`_`f definieren. Sie bestehen aus einem `F33f`_`[Knoten`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Knoten_(Graphentheorie)]`_`f `*w`*, der die Wurzel des Baumes darstellt, welcher ausschließlich mit den Wurzeln knotendisjunkter In-Trees `*T`*1, `*T`*2, …, `*T`*`*n`* in Richtung von `*w`* verbunden ist.

`c`F0af`_`[↑ Back to top`#top]`_`f`a